package com.lsa.letcode.the148.mergeSortList;

import com.lsa.letcode.common.ListNode;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
    	if (head == null) {
    		return null;
    	}
    	return mergeSort(new ListNode[]{head}, 0, size(head) - 1);
    }
    
    private int size(ListNode head) {
    	int size = 0;
    	while(head != null) {
    		size++;
    		head = head.next;
    	}
		return size;
	}
    
    ListNode mergeSort(ListNode[] n, int from, int to) {
    	if (from > to){
    		return null;
    	}
    	int mid = (from + to) >>> 1;
    	ListNode left = mergeSort(n, from, mid - 1);
    	ListNode cur = n[0]; 
    	n[0] = n[0].next;
    	cur.next = null;
    	return merge(merge(left, cur), mergeSort(n, mid + 1, to));
    }
    
    public ListNode merge(ListNode l1, ListNode l2) {
    	if (isEmpty(l1)) {
    		return l2;
    	}
    	else if (isEmpty(l2)) {
    		return l1;
    	}
    	
    	ListNode[] headPtr = new ListNode[1];
    	ListNode front = null;
    	
    	while(l1 != null || l2 != null) {
    		if (l1 != null && l2 != null) {
    			int cmp = compare(l1, l2);
    			if (cmp <= 0) {
    				front = append(front, l1, headPtr);
    				l1 = l1.next;
    			}
    			if (cmp >= 0) {
    				front = append(front, l2, headPtr);
    				l2 = l2.next;
    			}
    		}
    		else if (l1 != null){
    			front = append(front, l1, headPtr);
				break;
    			
    		}
    		else { // l2 != null
    			front = append(front, l2, headPtr);
    			break;
    		}
    	}
    	
        return headPtr[0];
    }
    
    private int compare(ListNode l1, ListNode l2) {
    	return l1.val - l2.val;
    }
    
    private ListNode append(ListNode front, ListNode l, ListNode[] head) {
    	if (front == null) {
    		front = l;
    		head[0] = front;
    	}
    	else {
    		front.next = l;
    		front = front.next;
    	}
    	return front;
    }
    
    private boolean isEmpty(ListNode l1) {
    	return l1 == null;
    }
}